'''
Created on 2010-3-3

@author: Administrator
'''
from jolly.datastructures.AbstractMethod import AbstractMethod
from jolly.datastructures.Container import Container
from jolly.datastructures.QueueAsLinkedList import QueueAsLinkedList
from jolly.datastructures.StackAsLinkedList import StackAsLinkedList
from jolly.datastructures.PrePostVisitor import PrePostVisitor
from jolly.datastructures.PreOrder import PreOrder
from jolly.datastructures.InOrder import InOrder
from jolly.datastructures.PostOrder import PostOrder
from jolly.datastructures.PrintingVisitor import PrintingVisitor
from jolly.datastructures.Iterator import Iterator
from jolly.datastructures.Visitor import Visitor

class Tree(Container):
    '''
    Base class from which all tree classes are derived.
    '''

    def getKey(self):
        pass
    getKey=AbstractMethod(getKey)
    key=property(fget=lambda self: self.getKey())
    
    def getSubtree(self, i):
        pass
    getSubtree=AbstractMethod(getSubtree)
    
    def getIsLeaf(self):
        pass
    getIsLeaf=AbstractMethod(getIsLeaf)
    isLeaf=property(fget=lambda self: self.getIsLeaf())
    
    def getDegree(self):
        pass
    getDegree=AbstractMethod(getDegree)
    degree=property(fget=lambda self: self.getDegree())
    
    
    
    
    
    def __init__(self):
        '''
        (Tree)->None
        Constructor.
        '''
        super(Tree, self).__init__()
    
    def depthFirstTraversal(self, visitor):
        '''
        (Tree, PrePostVisitor) -> None
        Makes the given visitor do a depth-first traversal of this tree.
        '''
        assert isinstance(visitor, PrePostVisitor)
        if not self.isEmpty and not visitor.isDone:
            visitor.preVisit(self.key)
            for i in xrange(self.degree):
                self.getSubtree(i).depthFirstTraversal(visitor)
            visitor.postVisit(self.key)
    
    PREORDER = -1
    INORDER = 0
    POSTORDER = +1
    
    def depthFirstGenerator(self, mode):
        '''
        (Tree) -> generator
        Yields the keys in this tree in depth-first traversal order.
        '''
        if not self.isEmpty:
            if mode==self.PREORDER:
                yield self.key
            for i in xrange(self.degree):
                for obj in self.getSubtree(i).depthFirstGenerator(mode):
                    yield obj
            if mode==self.POSTORDER:
                yield self.key
    
    def breadthFirstTraversal(self, visitor):
        '''
        (Tree, Visitor) -> None
        Makes the given visitor do a breadth-first traversal of this tree.
        '''
        assert isinstance(visitor, Visitor)  
        queue = QueueAsLinkedList()
        if not self.isEmpty:
            queue.enqueue(self)
        while not queue.isEmpty and not visitor.isDone:
            head = queue.dequeue()
            visitor.visit(head.key)
            for i in xrange(head.degree):
                child=head.getSubtree(i)
                if not child.isEmpty:
                    queue.enqueue(child)
                    
    def breadthFirstGenerator(self):
        '''
        (Tree) -> generator
        Yields the keys in this tree in depth-first traversal order.
        '''
        queue=QueueAsLinkedList()
        if not self.isEmpty:
            queue.enqueue(self)
        while not queue.isEmpty:
            head=queue.dequeue()
            yield head.key
            for i in xrange(head.degree):
                child=head.getSubtree(i)
                if not child.isEmpty:
                    queue.enqueue(child)
    
    def accept(self, visitor):
        '''
        (Tree) -> Visitor
        Makes the given visitor visit the nodes of this tree.
        '''
        assert isinstance(visitor, Visitor)
        self.depthFirstTraversal(PreOrder(visitor))
    
    def getHeight(self):
        '''
         (Tree) -> int
        Returns the height of this tree.
        '''
        if self.isEmpty:
            return -1
        height=-1
        for i in xrange(self.degree):
            height=max(height, self.getSubtree(i).height)
        return height+1
    height=property(fget=lambda self: self.getHeight())
    
    def getCount(self):
        '''
        (Tree)->int
        Returns the number of nodes in this tree.
        '''
        if self.isEmpty:
            return 0
        result=1
        for i in xrange(self.degree):
            result=result+self.getSubtree(i).count
        return result
    
    class Iterator(Iterator):
        '''
        Enumerates the nodes of a tree.
        '''
        
        def __init__(self, tree):
            '''
            (Tree.Iterator, Tree) -> None
            Constructs an iterator for the given tree.
            '''
            super(Tree.Iterator, self).__init__(tree)
            self._stack = StackAsLinkedList()
            if not tree.isEmpty:
                self._stack.push(tree)
        
        def next(self):
            '''
            (Tree.Iterator) -> Object
            Returns the next node in the tree.
            '''
            if self._stack.isEmpty:
                raise StopIteration
            top = self._stack.pop()
            i = top.degree-1
            while i>=0:
                subtree=top.getSubtree(i)
                if not subtree.isEmpty:
                    self._stack.push(subtree)
                i-=1
            return top.key
    
    def __iter__(self):
        '''
        (Tree) -> Tree.Iterator
        Returns an interator for this tree.
        '''
        return Tree.Iterator(self)

    @staticmethod
    def test(tree):
        "Tree test program."
        print Tree.test.__doc__
        visitor = PrintingVisitor()
        print tree
        print "Breadth-First traversal"
        tree.breadthFirstTraversal(visitor)
        visitor.finish()
        print "Preorder traversal"
        tree.depthFirstTraversal(PreOrder(visitor))
        visitor.finish()
        print "Inorder traversal"
        tree.depthFirstTraversal(InOrder(visitor))
        visitor.finish()
        print "Postorder traversal"
        tree.depthFirstTraversal(PostOrder(visitor))
        visitor.finish()
        print "Using iterator"
        for i in tree:
            print i
        print "Using depth-first generator (preorder)"
        for i in tree.depthFirstGenerator(Tree.PREORDER):
            print i
        print "Using breadth-first generator"
        for i in tree.breadthFirstGenerator():
            print i
        print tree.height
        print tree.count